package com.dwliu.sort;

public class ShellSort {
	/**
	 * sort array a.
	 * @param a
	 */
	public static void shellSort(int a[]){
		int i, j, gap;
		int n = a.length;
		for(gap = n; gap>0; gap/=2){
			
			//组内排序
			for(i = 0; i<gap; i++){
				
				//直接插入排序
				for(j=i+gap; j<n; j+=gap){
					
					//判断是否需要插入
					if(a[j]<a[j-gap]){
						int temp = a[j];
						int k=j-gap;//游标位置，将该位置上的值往后移动一位
						
						while(k>=0 && a[k]>temp){
							a[k+gap] = a[k];
							k -= gap;
						}
						a[k+gap] = temp;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a []= {1,6,3,4,5};
		for(int t: a)
			System.out.print(t+" ");
		System.out.println();
		shellSort(a);
		for(int t: a)
			System.out.print(t+" ");
	}
}
